桶排序

十大经典排序算法

桶排序（Bucket sort）是把数组放到 n 个桶里面，然后每个桶里个元素在分别单独排序，单独排序时候可以使用其他排序方式，桶的数量 n 并没有一个固定的值，可以自己定。使用桶排序的时候每个桶里的元素不是随便放的，要保证当前桶里最大值小于下一个桶的最小值。使用桶排序是时候我们需要先计算数组的最大值和最小值，比如有数组 [5,13,9,7,2,12,8] ，数组的最大值和最小值分别是 13 和 2 ，假设我们使用 3 个桶，那么每个桶里元素的范围就是 (13-2)/3+1=4 ，所以这 3 个桶每个桶里的元素区间分别为 [2，5] ， [6，9] ， [10，13] 。我们把数组中的元素放到 3 个桶里，分别为 [5，2] ， [9，7，8] ， [13，12] ，放完之后分别对每个桶进行单独排序，如下图所示。

private void bucketSort(int[] nums) {
    int length = nums.length;
    // 桶的数量，我们这里定义为3。
    int bucketSize = 3;
    // 分别计算数组的最大值和最小值。
    int max = Arrays.stream(nums).max().getAsInt();
    int min = Arrays.stream(nums).min().getAsInt();

    // 创建桶，这里使用list集合表示桶。
    List<List<Integer>> buckets = new ArrayList<>(bucketSize);
    for (int i = 0; i < bucketSize; i++) {
        buckets.add(new ArrayList<>());
    }

    // bucketRange表示桶中元素的范围。
    int bucketRange = (max - min) / bucketSize + 1;
    for (int i = 0; i < length; i++) {
        // 根据数组中元素的大小，把数组中的元素放到指定的桶里。
        buckets.get((nums[i] - min) / bucketRange).add(nums[i]);
    }

    int bucketIndex = 0;
    // 对每个桶在单独排序。
    for (int i = 0; i < buckets.size(); i++) {
        List<Integer> mList = buckets.get(i);
        // 每个桶里的元素在单独排序。
        Collections.sort(mList);
        for (int j = 0; j < mList.size(); j++) {
            nums[bucketIndex++] = mList.get(j);
        }
    }
}

稳定性分析

桶排序是先把数组中的元素放到桶里，然后每个桶再单独排序。放到桶里是从前往后遍历数组，不会打乱相同元素的相对位置，而每个桶里的排序我们可以使用稳定的排序算法，所以桶排序是稳定的。桶排序的时间复杂度依赖桶的大小，如果桶足够大，时间复杂度可以达到 n。

时间复杂度：n
稳定性：稳定

相关链接